SRM 643

Match Summary

Round Overview

Div2 250: TheKingsArmyDiv2

This problem requires more analysis than the average division 2 easy. The important thing to notice is to keep present the simulation of two happy soldiers who are initially neighbors:

This uses the ‘.’ character instead of ‘S’ for sad soldiers so that it is easier to notice the change. The two happy soldiers can tell each other a joke and …

Now many more soldiers are happy and each contiguous pair of them can tell each other a joke:

If we repeat this, eventually the whole army will be happy.

That’s all we need to know, whenever there are two soldiers next to each other, they can cause a chain reaction that’ll eventually make every soldier happy. The states of other soldiers do not affect the outcome.

This works in corner cases:

Note the soldiers can be neighbors horizontally or vertically:

Optimal number of awards

If there is at least one pair of contiguous happy soldiers (horizontally or vertically) then we can be certain that all soldiers will become happy.

If not then we need* to give awards. The maximum number of awards we need is 2: Make two contiguous soldiers happy. So we just need to detect the cases in which only one award is needed.

* This is because the problem is limited to at least 3 columns and at least 3 rows. If cases with only one row or only one column were allowed, then there would be cases in which there are no pairs of neighboring soldiers that still don’t need any awards.

If there is at least one happy soldier, we can always make a neighbor of the soldier happy and that will introduce a happy pair that can spread happiness with the previously-mentioned chain reaction. The result is 1.

In the other case, there are no happy soldiers, we will need to add two of them. The result is 2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int getNumber(vector < string > state) {
  int r = state.size(), c = state[0].size();
  bool hasH = false; // will be true if we find at least one H

  for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) {
      if (state[i][j] == 'H') {
        hasH = true;
        // vertical neighbor:
        if ((i + 1 < r) && (state[i + 1][j] == 'H')) {
          return 0;
        }
        // horizontal neighbor:
        if ((j + 1 < c) && (state[i][j + 1] == 'H')) {
          return 0;
        }
      }
    }
  }

  if (hasH) {
    return 1;
  } else {
    return 2;
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class TheKingsArmyDiv2:
  def getNumber(self, state):
  w = len(state)
h = len(state[0])
# at least one pair of vertical neighbors:
  if any(any(state[i][j] == 'H'
    and state[i + 1][j] == 'H'
    for i in range(w - 1)) for j in range(h)):
  return 0
# at least one pair of horizontal neighbors:
  if any(any(state[i][j] == 'H'
    and state[i][j + 1] == 'H'
    for j in range(h - 1)) for i in range(w)):
  return 0
# at least one happy soldier:
  if any(any(ch == 'H'
    for ch in s) for s in state):
  return 1
return 2

Div1 Hard: CasinoGame

The first thing to realise is that we can write the answer as \sum_{i=0}^{{N-1}\sum_{j=0}}{N-1}E[i][j]\cdot P[j], where P[j] is the probability that this element will be chosen in phase 1 of turn j, disregarding all effects applied on this element during phase 3 (which are taken into account in E[i][j]), and E[i][j] is the expected value of this element in this turn.

We can split E[i][j] further, accounting for the listed effects:

• if k turns have passed since the last “restore” effect applied on S[i], the probability of S[i] being restored during turn j-k-1 (we allow k=j here) is r[j-k] and the expected value that S[i] can take during those k turns without being restored is e[i][k], then E[i][j]=\sum_{k=0}^j r[j-k]\cdot e[i][k]

• the probability of any sequence of k “half” and “sqrt” effects being applied on S[i] is the same, 0.33^k, so we basically just need the sum of values of S[i] after all such sequences of effects; summing them up and multiplying by 0.33^k gives e[i][k]

• if there are l “sqrt” effects applied, then the contribution to e[i][k] can be written as 0.33^k \sqrt{S[i]}_l c[k][l], where \sqrt{.}_l means \sqrt{} being applied l times (the 0.5^l-th power) and c[k][l] is the sum of final values of S[i] over all sequences with given k,l if its inital value was S[i]=1 - the sum of all \prod_{m=0}^l 0.5^{q_m \cdot 0.5^m} over all l+1-tuples q_{0…l} such that k-l=\sum_{m=0}^l q_m

That is, each sequence of effects “half” and “sqrt” with given k,l is given by the numbers q_m, which describe how many “half” effects get applied on S[i] immediately after the l-m-th “sqrt” effect (the 0-th “sqrt” effect corresponds to the start of the sequence).

So, we only need to find out how to calculate P[], r[] and c[][].

In order to calculate P[], we need intermediate probabilities p[j][k] - that there will be k elements (other than our S[i]) non-erased right before turn j, since that affects the probability that S[i] will be chosen next. The positions of those elements or of S[i] don’t matter here. We can see that the following recurrence holds with p[0][N-1]=1:

($C(,)$ are binomial coefficients) since if there were l elements other than S[i] erased during phase 3 of turn j-1 and k non-erased elements after that phase concluded, then there were k+l+1 elements other than S[i] non-erased before turn j-1; the probability \frac{k+1+l}{k+2+l} is that of our S[i] not being the one erased in phase 1 and the rest is the probability of those exactly l out of k+l elements hitting “erase” effects multiplied by the number of ways to choose them (binomial coefficient). Note that the effects applied on S[i] aren’t considered here.

If we write D[k][l]=C(k+l,l)0.33^l(1-0.33)k, then we may notice that it satisfies the recurrence

with D[k][0]=(1-0.33)^k and D[0][l]=0.33^l, so the array D[][] can be computed easily. We can also use intermediate arrays v[j][k]=p[j][k]\frac{k}{k+1}. Then, we have p[j][k] = \sum v[j-1][k+1+l]D[k][l], which lets us compute p[][] in O(N^3) time. The formula which can be used to compute P[] is

Next up is r[]. Obviously, r[0]=1, since if j=k, we’re just starting the game and no effects have been applied. For r[j] with j > 0, the last effect must have been “restore”, with probability 0.01, and all effects before that could’ve been anything except “erase”, with probability (1-0.33)^{j-1}, so r[j > 0]=0.01\cdot(1-0.33)^{j-1}.

For c[][], we can construct a recurrent formula as well: c[k][0]=0.5^k and for l > 0, there are two cases/terms - the sum over sequences starting with an “sqrt” effect is c[k-1][l-1] and the sum over those starting with a “half” effect is \sqrt{0.5}_l c[k-1][l]. So we can precompute \sqrt{0.5}_l for all l and use the formula

to compute c[][] in O(N^2). We pretty much know the rest:

This lets us compute the answer in O(N^3). Fortunately, the part that causes the time complexity to be O(N^3) instead of O(N^2) is just a few double loops with simple sums and few multiplications (we can also multiply c[k][l] by 0.33^k ahead of time) and N=1000 is pretty small, so it can fit into the time limit. If it doesn’t, there’s still another possible optimisation: we may notice that many things will often be very small for large k and we don’t have to sum up over them for all k.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
typedef vector < double > vec;
typedef vector < vec > vec2;
// because they're like the only array types we're ever going to use

class CasinoGame {
  typedef vector < double > vec;
  typedef vector < vec > vec2;
  // because they're like the only array types we're ever going to use

  class CasinoGame {
    public: double expectedValue(vector < int > S) {
      int N = S.size();

      vec2 D(N + 1, vec(N + 1, 0));
      D[0][0] = 1;
      for (int i = 1; i <= N; i++) D[0][i] = 0.33 * D[0][i - 1];
      for (int i = 1; i <= N; i++) {
        D[i][0] = D[i - 1][0] * (1 - 0.33);
        for (int j = 1; j <= N; j++) D[i][j] = 0.33 * D[i][j - 1] + (1 - 0.33) * D[i - 1][j];
      }

      vec2 p(N + 1, vec(N + 1, 0));
      p[0][N - 1] = 1;
      for (int i = 1; i <= N; i++) {
        vec v = p[i - 1];
        for (int j = 0; j <= N; j++) v[j] *= 1.0 * j / (j + 1);
        for (int j = 0; j <= N - i + 1; j++)
          for (int k = 0; k <= N - 1 - j; k++) p[i][j] += v[j + 1 + k] * D[j][k];
      }

      vec P(N + 1, 0);
      for (int i = 0; i <= N; i++)
        for (int j = 0; j < N; j++) P[i] += p[i][j] / (j + 1);

      vec r(N + 1, 1);
      for (int j = 1; j <= N; j++) r[j] = r[j - 1] * ((j == 1) ? 0.01 : (1 - 0.33));

      vec sq(N + 1, 0.5);
      for (int i = 1; i <= N; i++) sq[i] = sqrt(sq[i - 1]); // i times sqrt-ed 0.5

      vec2 c(N + 1, vec(N + 1, 0));
      c[0][0] = 1;
      for (int i = 1; i <= N; i++) {
        c[i][0] = 0.5 * c[i - 1][0];
        for (int j = 1; j <= N; j++) c[i][j] = c[i - 1][j - 1] + sq[j] * c[i - 1][j];
      }

      vec2 SS(N + 1, vec(N + 1, 0)); // SS[i][j]: i-times sqrt-ed S[j]
      for (int i = 0; i < N; i++) SS[0][i] = 0.001 * S[i];
      for (int i = 1; i <= N; i++)
        for (int j = 0; j < N; j++)
          SS[i][j] = sqrt(SS[i - 1][j]);

      for (int i = 0; i <= N; i++) { // c[j][k] -> c[j][k]*0.33**j
        double d = pow(0.33, i);
        for (int j = 0; j <= N; j++) c[i][j] *= d;
      }
      vector < vector < int > > nz(N + 1); // non-negligible entries of c[][]
      for (int i = 0; i <= N; i++)
        for (int j = 0; j <= i; j++)
          if (c[i][j] > 1e-30) nz[i].push_back(j);
      vec2 e(N + 1, vec(N + 1, 0));
      for (int i = 0; i < N; i++)
        for (int j = 0; j <= N; j++)
          for (int k = 0; k < (int) nz[j].size(); k++) e[i][j] += SS[nz[j][k]][i] * c[j][nz[j][k]];

      vec2 E(N + 1, vec(N + 1, 0));
      for (int i = 0; i < N; i++)
        for (int j = 0; j <= N; j++)
          for (int k = 0; k <= j; k++) E[i][j] += r[j - k] * e[i][k];

      double ans = 0;
      for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) ans += E[i][j] * P[j];
      return ans;
    }
  };
  </vec> < /double>

Div2 500 / Div1 250: TheKingsFactorization

The known factors

There is a number N and some known prime factors of it. We need to find the other prime factors. The number is up to 10^18, so the usual O(sqrt(N)) algorithm we’d use to factorize a number through trial division cannot be used here.

One thing we can do is divide the initial number by the known prime factors and then factorize the remaining number. Since we have half of the prime factors, the new number to factorize will be smaller than N, but it won’t necessarily be significantly smaller. Imagine an example like 2 multiplied by a very large prime number. The known factor will be 2 and then we will still need to factorize the large prime number. Even if we take care of this case with only two factors in an ad hoc way, we can find numbers with 10 factors that would still leave us with a huge number to factorize. For example: 2*2*2*2*2*2*2*7812499999999979 = 999999999999997312, the input would be: {2,2,2,2} and we would need to factorize 62499999999999832.

How to factor in quadratic time

As the challenge phase statistics show, it was very easy to come up with a wrong solution to this problem. We should find a solution that we can be certain to be correct. A way to reach this solution is to first make sure we understand why we can solve prime factorization in O(sqrt(N)) time.

The division by trial algorithm to factorize a number is very simple: Initialize x = N, then just try numbers p from 2 to sqrt(N), every time x is a multiple of p, divide x by p and add p to the list. If after all of it, x is larger than 1, then it is also a prime factor:

Why do we only need to try p up to sqrt(x)? Because we can assume that the largest prime factor of N will be found as x in the last step of this algorithm. We have a prime factorization like: p_0 * p_1 * p_2 * … * p_t and assume that, as long as we find all the smaller prime factors, then dividing N by these prime factors will yield the largest one: p_t.

Because we do not need to visit the largest prime factor, we must make sure that the values of p visit up to the second-largest prime factor. If we assume that there is at least one prime factor q >= p, then we need to find the maximum p such that: p*q <= N, remember that q >= p, therefore, q will be at least p, which means that p*p <= N must be true: p <= sqrt(N).

The third-largest prime factor

Back to the original problem, there are many prime factors of N that we do not need to find. All prime factors with even index in the factorization are already included in the input and we do not need to look for them. Sometimes, the second-largest prime factor is already known. This depends on whether the number of prime factors is even or odd.

• If the number of prime factors of N is even, then the largest prime factor will have odd index. It will not be present in the input.

• If the number of prime factors of N is odd, then the largest prime factors will have even index. And will be present in the input.

Even case

The number of prime factors is even, the largest prime factor is not in the input so we need to find it, the second-largest prime factor is in the input, so we do not need to find it. The third-largest prime factor (if it exists) is not in the input, so we need to find it.

This is good. If we use the trial by division algorithm and we stop after a number that is guaranteed to cover the third-largest prime number, then we can be certain that whatever is left after dividing all the factors we find will be the largest prime number.

Like in the previous proof, we need to make sure to look for values of p such that the third-largest prime factor of N is visited. We have q >= p and r >= q, ergo: pqr <= N becomes p^3 <= N and thus we need to find values of p up to root3 N. An O(root3 N) algorithm.

Odd case

The largest prime factor is in the input. The second-largest prime factor (if it exists) is not in the input and we need to find it. The third-largest prime factor is in the input. The fourth-largest prime factor (if it exists) is not in the input and we need to find it. Using the same logic as before, we need to find values of p up to root4 N, which is covered by the previous bound.

Code

In reality, for the case to be even, we need at least one prime factor exists before the third-largest prime, so we can assume that this prime factor is at least 2. And then we visit values of p until 2p^3 > N, this slightly reduces the upper bound but is unnecessary. But this helps us show that 793699 is the largest number we need to look for, so that we can solve this case: { 999994232152622198, {2,793699} }.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector < long long > getVector(long long N, vector < long long > primes) {
  long long n = N;
  for (auto p: primes) {
    n /= p;
  }
  for (long long p = 2; 2 * p * p * p <= N; p++) {
    while (n % p == 0) {
      n /= p;
      primes.push_back(p);
    }
  }
  if (n > 1) {
    primes.push_back(n);
  }
  sort(primes.begin(), primes.end());
  return primes;
}

Div2 1000: TheKingsTree

Trees are a recursive data structure, many problems involving trees are solvable using a recursive logic. Let’ try it. So we should try solving the problem for each subtree rooted at a node x. Begin with a function f(x) that returns the minimum cost of coloring the subtree rooted at x.

The first issue is that we cannot know the cost of coloring node x red or green before we color the other contents in the subtree. In reality, the specific positions of the colors in the children of x do not really matter. What we need to know is the number of red and green nodes in the subtree. Since the total number of vertices in the subtree can be calculated by adding them up all recursively, then we only need the number of red nodes. So we can try any valid r : the number of red nodes in the subtree. Given r we can choose the color of x

• If we color node x red, the cost of coloring the vertex is r. We can proceed to fill the remaining nodes. So we end up in a new subproblem. We need to choose the minimum cost method to color the remaining vertices in this subtree, with the condition that r-1 of them must be red. (We already colored one of the r red vertices)

• Color node x green. If there are s vertices in the subtree, the cost would be the number of green nodes in the subtree: s - r. Then we are in the same subproblem as before, only that this time r of the remaining vertices must be red.

The result would be the minimum among all r.

Coloring (grand)children

For the subproblem, we need to color all the vertices in the subtree rooted at x (x is already colored). We must color r of them red.

We must first now the number of children of x, let’s name it t.

If t = 0, then x has no children. There are no vertices we can color. If r = 0, then we can just return 0, as that’s the minimum cost to color 0 vertices red. But if r > 0, this case would be invalid, there are no vertices to color. We can work around this by avoiding creating this situation or by making this situation return a very large number (Since this is a minimization problem, if a large number is returned, the case wouldn’t be used, as valid cases will have smaller results).

When (t > 0), we should try to exploit the recursive nature of the tree. A simple way to do this is to first index the children of x. Imagine there are t children of x, each will get a unique index from 0 to t-1.

There is a whole subtree rooted at child # t-1. We already know how to color the optimal number of vertices in this subtree red - By calling f(). Name this child vertex y. f(y) would return the minimum cost of coloring the tree rooted at y. However, we need to first establish the number of red vertices, and the number of red vertices affects our requirement for x. The fix is to modify our idea of f(), this time it needs both a node x and a fixed number of red vertices: f_1(x,r) (To solve the initial case f(x) we used in the previous version, just pick the minimum f_1(x,r) for all possible values of r ).

Imagine the number of vertices in the subtree rooted at y was s. We can try and pick any number q of red vertices between 0 and min(r,s) for the subtree rooted at y. The minimum cost would be f_1(y,q). We still need to fill the colors in the remaining subtrees. But note that this is the same as solving the original subproblem but with t-1 subtrees instead of t with r-q red vertices.

To flesh out the solution to this subproblem, we can think of a new function f_2(x,t,r), finds the minimum cost to color the t first children of x using r red vertices. Then we try every value of q for the number of red vertices used in vertex y (where y is child # t-1 of x). Calculate: f_1(y,q) + f_2(x, t-1, r-q).

Code

The recursive logic is acyclic and we can just use some memoization or make sure to fill the results for the vertices in bottom to top order ( the vertices are already topsorted in the input)

This c++ solution fills the results for each subtree from bottom to top.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
int getNumber(vector < int > parent) {
  const int INF = 1000000000;
  int n = parent.size() + 1;
  // g[x] will hold a vector of children of x
  vector < vector < int >> g(n);
  for (int i = 0; i < n - 1; i++) {
    g[parent[i]].push_back(i + 1);
  }

  int subtreeSize[n];
  int f1[n][n + 1];
  int f2[n][n][n + 1];

  for (int x = n - 1; x >= 0; x--) {
    subtreeSize[x] = 1;
    for (int y: g[x]) {
      subtreeSize[x] += subtreeSize[y];
    }

    // f2:
    // base case:
    int t = g[x].size();
    f2[x][0][0] = 0; // used all edges, no red vertices
    for (int r = 1; r <= n; r++) {
      f2[x][0][r] = INF; // red vertices, meaning we didn't assign enough of them
    }
    for (int i = 1; i <= t; i++) {
      for (int r = 0; r <= n; r++) {
        int mx = std::min(subtreeSize[g[x][i - 1]], r);
        f2[x][i][r] = INF;
        for (int q = 0; q <= mx; q++) {
          int cost = f1[g[x][i - 1]][q] + f2[x][i - 1][r - q];
          f2[x][i][r] = std::min(f2[x][i][r], cost);
        }
      }
    }

    //f1:
    for (int r = 0; r <= n; r++) {
      // pick x's color
      f1[x][r] = INF;
      if (r > 0) {
        // pick red
        f1[x][r] = r + f2[x][t][r - 1];
      }
      int s = subtreeSize[x];
      if (s - r > 0) {
        // pick green
        f1[x][r] = std::min(f1[x][r], s - r + f2[x][t][r]);
      }
    }
  }

  // pick number of red vertices:
  int res = INF;
  for (int r = 0; r <= n; r++) {
    res = std::min(res, f1[0][r]);
  }
  return res;
}

This python solution uses the recursive logic and memoizes it:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
INF = 10 ** 9

class TheKingsTree:
  def getNumber(self, parent):
  n = len(parent) + 1
#g[i] holds a list of all children of i
g = [[i
    for i in range(1, n) if parent[i - 1] == j]
  for j in range(n)]

@memoize_this_function #function decorators are so useful
def subtreeSize(x):
  return 1 + (sum(subtreeSize(y) for y in g[x]) if len(g[x]) > 0
    else 0)

@memoize_this_function
def f2(x, t, r):
  if t == 0:
  # base
case
return INF
if (r > 0)
else 0
else:
  mx = min(subtreeSize(g[x][t - 1]), r)
return min(f1(g[x][t - 1], q) + f2(x, t - 1, r - q) for q in range(mx + 1))

@memoize_this_function
def f1(x, r):
  res = INF
# pick x 's color
if r > 0:
  # pick red:
  res = r + f2(x, len(g[x]), r - 1)

s = subtreeSize(x)
if s - r > 0:
  # pick green:
  res = min(res, s - r + f2(x, len(g[x]), r))
return res

#pick the minimum f(0, r) possible where r is the number of red vertices
return min(f1(0, r) for r in range(0, n + 1))

def memoize_this_function(f):
  mem = dict()
def g( * args):
  try:
  return mem[args]
except(KeyError):
  x = f( * args)
mem[args] = x
return x
return g

Div1 Medium: TheKingsArmyDiv1

Te alternating case

There are 4 possible kinds of columns in the input:

We can try and solve a simplified version of the problem. For example, what if the only allowed columns in the input were those that have one happy and one sad soldier.

In this easier variation the only moves that are useful are those that make a contiguous group of soldiers in the same row greet the equivalent soldiers in the other row (horizontal move). The other moves are not helpful. Individual handshake and the vertical move will convert at most one soldier, which the horizontal move can also convert while maybe converting many others.

If we only use horizontal moves, we need to recognize that the following cases are all equivalent:

To the horizontal move, a contiguous group of happy soldiers with an equivalent group of sad soldiers in the other row is always the same no matter the length.

So now we can try to find the number of moves needed for different cases:

There is really only one group. We can make all happy soldiers make the others happy in 1 move.

When there are two groups, we need two steps. There are two horizontal moves we can try, both will turn the case into one of the next cases:

In both situations, we can ignore the happy columns because they are at the extremes. There is one group, which needs an extra step. 2 steps in total.

When there are 3 groups, things become interesting:

You can use the move on the middle group:

There are now columns with two happy soldiers, but surprisingly, we can still ignore them. The following two moves are equivalent:

When there are two happy soldiers in a column, they do not interfere with the horizontal moves we would use. This effectively reduces the number of groups by 2.

Whenever there are at least 3 groups, we can reduce the number of groups by one in a single move. f(1) = 1, f(2) = 2, f(n >= 3) = 1 + f(n-2). We can find it by dividing |__n / 2__| + 1 where |__x__| is the floor() function, meaning that we round down, or we are using integer division.

Two happy soldiers

Now we can just try adding the possibility that there might be two happy soldiers in a single column. The problem doesn’t really change much:

We can deal with these happy columns in the input the same way we dealt with when using only horizontal moves. We can ignore these columns.

Two sad soldiers

What if there are two sad soldiers in the same column? Ignoring the corner case when all soldiers are sad; There will always be at least one column that has a happy soldier.

The idea is to use vertical moves to replace these sad columns with other columns. This part is interesting, it doesn’t matter which column(s) you pick. Remember, when solving the rest of the problem, columns with 2 happy soldiers can be ignored and the the length of the HS and SH groups doesn’t change the answer. Replacing the SS columns with anything else will require one move for each of the SS columns.

Code

We are ready to implement the algorithm, first treating HH and SS columns separately and then using the formula for the other teams.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int getNumber(vector < string > state) {
  int n = state[0].size();
  int countSS = 0, countHH = 0;
  vector < string > difs;
  for (int i = 0; i < n; i++) {
    if (state[0][i] == 'S' && state[1][i] == 'S') {
      countSS++;
    } else if (state[0][i] == 'S') {
      difs.push_back("SH");
    } else if (state[1][i] == 'S') {
      difs.push_back("HS");
    } else {
      countHH++;
    }
  }
  if (countSS == n) {
    return -1;
  } else if (countHH == n) {
    return 0;
  } else if (difs.size() == 0) {
    return countSS;
  }
  int changes = 0;
  for (int i = 1; i < difs.size(); i++) {
    if (difs[i] != difs[i - 1]) {
      changes++;
    }
  }

  return (changes + 1) / 2 + 1 + countSS;

}